package top100;

/**
 * @author Godc
 * @description
 */
public class MinWindow {
    public static void main(String[] args) {
        MinWindowSolution s = new MinWindowSolution();
        s.minWindow("ADOBECODEBANC","ABC");
    }
}
class MinWindowSolution {
    public String minWindow(String s, String t) {
        int[] hash = new int[128];
        String res = null;
        int cnt = 0;
        int max = s.length()+1;
        for(int i = 0;i<t.length();i++){
            hash[t.charAt(i)]--;
        }
        char[] chars = s.toCharArray();
        for(int i = 0,j = 0;i<chars.length;i++){
            char ch = chars[i];
            hash[ch]++;
            if(hash[ch]<=0) cnt++;
            while(j<i&&hash[chars[j]]>0) {
                hash[chars[j++]]--;
            }
            if (cnt==t.length()&&max>i-j+1)
            {
                max=i-j+1;
                res=s.substring(j,i+1);
            }
        }
        return res;
    }
}